#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>

typedef struct Node {
	Node* lchild;
	Node* rchild;
	int c;
} Node;
Node Tree[100];

int Ioc;
Node* creat()
{
	Tree[Ioc].lchild = Tree[Ioc].rchild = NULL;
	return (&Tree[Ioc++]);
}
void PostOrder(Node* T)
{
	if (T->lchild != NULL)
	{
		postOrder(T->lchild);
	}
	if (T->rchild != NULL)
	{
		postOrder(T->rchild);
	}
	printf("%d ", T->c);
}

void MidOrder(Node* T)
{
	if (T->lchild != NULL)
	{
		postOrder(T->lchild);
	}
	printf("%d ", T->c);
	if (T->rchild != NULL)
	{
		postOrder(T->rchild);
	}
}

void PreOrder(Node* T)
{
	printf("%d ", T->c);
	if (T->lchild != NULL)
	{
		postOrder(T->lchild);
	}
	if (T->rchild != NULL)
	{
		postOrder(T->rchild);
	}
}

Node* Insert(Node* T, int x)
{
	if (T == NULL)
	{
		T = creat();
		T->c = x;
	}
	else if (x < T->c)
	{
		T->lchild = Insert(T->lchild, x);
	}
	else if (x > T->c)
	{
		T->rchild = Insert(T->rchild, x);
	}
	return T;
}
int main()
{
	int n;
	while (scanf("%d", &n) != EOF)
	{
		Ioc = 0;
		Node* T = NULL;
		for (int i = 0; i < n; i++)
		{
			int x;
			scanf("%d", &x);
			T = Insert(T, x);
		}
		PreOrder(T);
		puts("\n");
		MidOrder(T);
		puts("\n");
		PostOrder(T);
		puts("\n");
	}
	return 0;
}